﻿using System;
using System.Collections.Generic;
using Algoritmia.Schemes;
using Algoritmia.StateSpaces;

namespace Algoritmia.Problems.RegularExpressions.Backtracking
{
    public class RegularExpressionMatchingStateSpace : IForwardStateSpace<RegularExpressionMatchingStateSpace.State,Tuple<int,int>>
    {
        private readonly string _s;
        private readonly NFASet.Nfa _nfa;

        public class State
        {
            public int Index { get; private set; }
            public int Q { get; private set; }

            public State(int index, int state)
            {
                Index = index;
                Q = state;
            }

            public static State CreateFromTuple(Tuple<int,int> tp)
            {
                return new State(tp.Item1,tp.Item2);
            }

            public Tuple<int, int> ToTuple()
            {
                return new Tuple<int, int>(Index, Q);
            }

        }
        public RegularExpressionMatchingStateSpace(NFASet.Nfa nfa, string s)
        {
            _s = s;
            _nfa = nfa;
        }

        #region Implementation of IForwardStateSpace<State,Tuple<int,int>>

        public State Decide(State state, Tuple<int, int> decision)
        {
            return State.CreateFromTuple(decision);
        }

        public IEnumerable<Tuple<int, int>> Decisions(State state)
        {
            if ( state.Index < _s.Length)
            {
                foreach(var r in _nfa.Destinations(state.Q,_s.Substring(state.Index,1)))
                {
                    yield return new Tuple<int, int>(state.Index+1,r);
                }
            }
            foreach (var r in _nfa.Destinations(state.Q, ""))
            {
                yield return new Tuple<int, int>(state.Index, r);
            }
        }

        public IEnumerable<State> InitialStates
        {
            get { yield return new State(0,_nfa.Start); }
        }

        public bool IsFinal(State state)
        {
            return state.Index == _s.Length && state.Q == _nfa.End;
        }

        #endregion
    }

    public class RegularExpressionMatcher : IRegularExpressionMatcher
    {
        private readonly NFASet.Nfa _nfa;
        private readonly BacktrackingEnumerator<RegularExpressionMatchingStateSpace.State, Tuple<int, int>, Tuple<int, int>> _enumerator;

        public RegularExpressionMatcher(string expression)
        {
            _nfa = new ThompsonAutomatonBuilder().Build(new RegularExpressionParser().Parse(expression));
            _enumerator =
                new BacktrackingEnumerator<RegularExpressionMatchingStateSpace.State, Tuple<int, int>, Tuple<int, int>>((space,i,d,f) => f.ToTuple());
        }

        public bool Match(string s)
        {
            bool r = true;
            try
            {
                _enumerator.First(new RegularExpressionMatchingStateSpace(_nfa,s));
            }
            catch (InvalidOperationException)
            {
                r = false;
            }
            return r;
        }
    }
}
